#include "BTreeNode.h"
#include<iostream>
/*
#include<cstdlib>
#include<fstream>
#include<sstream>
#include<cmath>
#include<string>
*/

using namespace std;

BTLeafNode::BTLeafNode() : m_numkeys(0) {
  memset(buffer, 0, PageFile::PAGE_SIZE);
}
BTNonLeafNode::BTNonLeafNode() : m_numkeys(0) {
  memset(buffer, 0, PageFile::PAGE_SIZE);
}

// Debugging function to print the contents of a BTnode buffer
void printBytes(char * buffer)
{
  int vals[PageFile::PAGE_SIZE / sizeof(int)];
  bool isPid = true;

  for (int i = 0; i < (PageFile::PAGE_SIZE-4); i=i+4)
  {
    if (i%8 == 0 && i != 0)
      cout << endl;

    vals[i/4] = ((int*) buffer)[i];

    if (isPid)
      cout << "pageid: ";
    else
      cout << "  key:    ";
    isPid = !isPid;

    printf("%02x %02x %02x %02x (%d) ",
        buffer[i], buffer[i+1], buffer[i+2], buffer[i+3], vals[i/4]);

  }
  cout << endl;
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{
	return pf.read(pid,buffer);
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{
	return pf.write(pid,buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{
  return m_numkeys;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{
	int keyCount = getKeyCount();
	int maxKeyCount = (PageFile::PAGE_SIZE - sizeof(PageId))/(sizeof(RecordId)+sizeof(int));

	if (keyCount >= maxKeyCount) {
		//cout << "Node is full" << endl;
		return RC_NODE_FULL;
	}

	RecordId tempRecordIdOne = rid;
	int tempKeyOne = key;
	RecordId tempRecordIdTwo;
	int tempKeyTwo;

	int eid;
	if (locate(key, eid) == RC_NO_SUCH_RECORD)  //eid contains entry where rid,key should be inserted
		eid = keyCount;

	int startIndex = eid*(sizeof(RecordId) + sizeof(int)); //bufIndex now contains first index in buffer where rid,index should be inserted

	int bufIndex;
	for (bufIndex = startIndex; bufIndex <= keyCount*(sizeof(RecordId)+sizeof(int)); bufIndex += (sizeof(RecordId) + sizeof(int)))
	{
		//cout << "record id sid: " << tempRecordIdOne.sid << endl;
		//cout << "key: " << tempKeyOne << endl;

		memcpy(&tempRecordIdTwo.pid, &buffer[bufIndex], sizeof(PageId));
		memcpy(&tempRecordIdTwo.sid, &buffer[bufIndex + sizeof(PageId)], sizeof(int));
		memcpy(&tempKeyTwo, &buffer[bufIndex + sizeof(RecordId)], sizeof(int));

		memcpy(&buffer[bufIndex], &tempRecordIdOne.pid, sizeof(PageId));
		memcpy(&buffer[bufIndex + sizeof(PageId)], &tempRecordIdOne.sid, sizeof(int));
		memcpy(&buffer[bufIndex + sizeof(RecordId)], &tempKeyOne, sizeof(int));

		tempRecordIdOne = tempRecordIdTwo;
		tempKeyOne = tempKeyTwo;
	}

  m_numkeys += 1;
	return 0;
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY
 *                    when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{
  if (sibling.getKeyCount() != 0)
    return RC_INVALID_ATTRIBUTE;

  if (getKeyCount() != BTLN_MAX_KEYS)
    return RC_INVALID_ATTRIBUTE;

  RC ret;

  // Loop through the buffer to find the spot for insertion (the first key
  // that's bigger). If our new key is the biggest one, i will automatically
  // point to the end.
  int i;
  for (i = 0; i < BTNLN_MAX_KEYS; ++i)
    if (getKeyAtEid(i) > key)
      break;

  // Make a temporary buffer to help insert the rid and key
  char * bigbuf = new (nothrow) char[PageFile::PAGE_SIZE +
                                     sizeof(rid) + sizeof(key)];
  if (bigbuf == 0)
    return RC_INVALID_CURSOR;

  // Determine the amount of space taken up by all the rids and keys
  // before the new one.
  int preBytes = i * (sizeof(RecordId) + sizeof(key));

  memcpy(bigbuf, buffer, preBytes);
  memcpy(bigbuf + preBytes, &rid, sizeof(RecordId));
  memcpy(bigbuf + preBytes + sizeof(RecordId), &key, sizeof(key));
  memcpy(bigbuf + preBytes + sizeof(RecordId) + sizeof(key),
         buffer + preBytes, PageFile::PAGE_SIZE - preBytes);

  // Set the sibling key
  int sibRidIndex = ((getKeyCount()+1) / 2)*(sizeof(RecordId) + sizeof(int));
  int sibKeyIndex = sibRidIndex + sizeof(RecordId);
  siblingKey = ((int *) bigbuf)[sibKeyIndex/sizeof(int)];

  // Use the bigbuf to populate this node with everything before the sibling
  // key. Also set the next node pointer.
  memset(buffer, 0, PageFile::PAGE_SIZE);
  memcpy(buffer, bigbuf, sibRidIndex);
  m_numkeys = (m_numkeys + 1)/2;

  ret = setNextNodePtr((PageId) &sibling);
  if (ret != 0)
  {
    delete [] bigbuf;
    return ret;
  }

  // Populate the sibling
  // TODO Where should the pid of the last sibling point to?
  RecordId currRid;
  int currKey;
  for (int j = sibRidIndex;
           j < PageFile::PAGE_SIZE;
           j += (sizeof(RecordId) + sizeof(int)))
  {
    memcpy(&currRid, bigbuf + j, sizeof(RecordId));
    memcpy(&currKey, bigbuf + j + sizeof(RecordId), sizeof(int));

    ret = sibling.insert(currKey, currRid);
    if (ret != 0)
    {
      delete [] bigbuf;
      return ret;
    }
  }

  delete [] bigbuf;

  return 0;

}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty
 *                 to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{
	//Testing purposes
	/*int firstkey,secondkey,thirdkey,fourthkey;
	memcpy(&firstkey, &buffer[8], sizeof(int));
	memcpy(&secondkey, &buffer[20], sizeof(int));
	memcpy(&thirdkey, &buffer[32], sizeof(int));
	memcpy(&fourthkey, &buffer[44], sizeof(int));
	cout << "first key: " << firstkey << endl;
	cout << "second key: " << secondkey << endl;
	cout << "third key: " << thirdkey << endl;
	cout << "fourth key: " << fourthkey << endl;*/


	int entryCounter = 0;
	int numKeys = getKeyCount();
	int bufIndex = sizeof(RecordId);
	if (numKeys == 0) {
//		cout << "No such key exists" << endl;
		return RC_NO_SUCH_RECORD;
	}

	int curKey;
	memcpy(&curKey, &buffer[bufIndex], sizeof(int));
	while(curKey < searchKey ) {
		bufIndex += (sizeof(RecordId) + sizeof(int));
		if (entryCounter >= numKeys) { //didn't find key
//			cout << "No such key exists" << endl;
			return RC_NO_SUCH_RECORD;
		}
		entryCounter++;
		memcpy(&curKey, &buffer[bufIndex], sizeof(int));
	}
	//cout << "entryCounter: " << entryCounter << endl;
	eid = entryCounter;
	return 0;
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{
	if (eid >= getKeyCount()) {
		//cout << "Record is out of bounds" << endl;
		return RC_INVALID_RID;
	}
	int startIndex = eid*(sizeof(RecordId) + sizeof(int));

	memcpy(&rid.pid, &buffer[startIndex], sizeof(PageId));
	memcpy(&rid.sid, &buffer[startIndex+sizeof(PageId)], sizeof(int));
	memcpy(&key, &buffer[startIndex+sizeof(RecordId)], sizeof(int));

	return 0;
}

/*
 * Return the pid of the next sibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{
	/*
	//Testing purposes
	int val = 1000;
	memcpy(&buffer[1020], &val, sizeof(int));
	*/

	PageId res;
	memcpy(&res, &buffer[PageFile::PAGE_SIZE - sizeof(PageId)], sizeof(PageId));
	return res;
}

/*
 * Set the pid of the next sibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{
	if (pid < 0) {
		//cout << "Invalid Page ID" << endl;
		return RC_INVALID_PID;
	}

	memcpy(&buffer[PageFile::PAGE_SIZE - sizeof(PageId)], &pid, sizeof(PageId));
	return 0;
}

void BTLeafNode::printBuffer()
{
  printBytes(buffer);
}

int BTLeafNode::getKeyAtEid(int eid)
{
  int offset = sizeof(RecordId) + eid*(sizeof(RecordId) + sizeof(int));
  return ((int *) buffer)[offset/sizeof(int)];
}

RecordId BTLeafNode::getRidAtEid(int eid)
{
  return ((RecordId *) buffer)[eid/sizeof(RecordId)];
}


/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{
  return pf.read(pid, (void*) buffer);
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{
  return pf.write(pid, (void*) buffer);
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{
  return m_numkeys;
}

/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{
  if (getKeyCount() == BTNLN_MAX_KEYS)
    return RC_NODE_FULL;

  // Find the right spot to put in our key and pid
  int i;
  for (i = 0; i < getKeyCount(); ++i)
    if (getKeyAtEid(i) > key)
        break;

  // From i (the eid) we calculate the byte offset to insert into. This offset
  // is the location of the first key bigger than the new key
  int offset = sizeof(PageId) + i*(sizeof(int) + sizeof(PageId));

  // Save the contents of the rest of the buffer
  int restSize = PageFile::PAGE_SIZE - offset - sizeof(int) - sizeof(PageId);
  char * rest = new (nothrow) char[restSize];
  if (rest == 0)
    return RC_INVALID_CURSOR;
  memcpy(rest, buffer + offset, restSize);

  // Put key and pid into the buffer and copy the rest of the buffer to the
  // right spot.
  memcpy(buffer + offset, &key, sizeof(key));
  memcpy(buffer + offset + sizeof(key), &pid, sizeof(pid));
  m_numkeys += 1;
  memcpy(buffer + offset + sizeof(key) + sizeof(pid), rest, restSize);

  delete [] rest;
  return 0;
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty
 *                    when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should
 *                    be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling,
    int& midKey)
{
  if (sibling.getKeyCount() != 0)
    return RC_INVALID_ATTRIBUTE;

  if (getKeyCount() != BTNLN_MAX_KEYS)
    return RC_INVALID_ATTRIBUTE;

  RC ret;

  // Loop through the buffer to find the spot for insertion (the first key
  // that's bigger). If our new key is the biggest one, i will automatically
  // point to the end.
  int i;
  for (i = 0; i < BTNLN_MAX_KEYS; ++i)
  {
    if (getKeyAtEid(i) > key)
      break;
  }

  // Make a temporary buffer to find the mid-key
  char * bigbuf = new (nothrow) char[PageFile::PAGE_SIZE +
                                     sizeof(key) + sizeof(pid)];
  if (bigbuf == 0)
    return RC_INVALID_CURSOR;

  // Determine the amount of space taken up by all the pids and keys before
  // our insertion.
  int preBytes = sizeof(pid) + i*(sizeof(key) + sizeof(pid));

  memcpy(bigbuf, buffer, preBytes);
  memcpy(bigbuf + preBytes, &key, sizeof(key));
  memcpy(bigbuf + preBytes + sizeof(key), &pid, sizeof(pid));
  memcpy(bigbuf + preBytes + sizeof(key) + sizeof(pid),
         buffer + preBytes, PageFile::PAGE_SIZE - preBytes);

  int midKeyIndex =
    sizeof(PageId) + ((getKeyCount()+1) / 2)*(sizeof(int) + sizeof(PageId));
  midKey = ((int *) bigbuf)[midKeyIndex/sizeof(int)];

  // Set our buffer to be half of bigbuf
  memset(buffer, 0, PageFile::PAGE_SIZE);
  memcpy(buffer, bigbuf, midKeyIndex);
  m_numkeys = (m_numkeys + 1)/2;

  // The pid after the midkey, the supplied key, and the supplied pid
  // go into the sibling node.
  PageId pid1AfterMidKey = ((PageId *) bigbuf)[midKeyIndex/sizeof(PageId) + 1];
  int keyAfterMidKey     = ((int *)    bigbuf)[midKeyIndex/sizeof(int)    + 2];
  PageId pid2AfterMidKey = ((PageId *) bigbuf)[midKeyIndex/sizeof(PageId) + 3];

  ret = sibling.initializeRoot(pid1AfterMidKey,keyAfterMidKey,pid2AfterMidKey);
  if (ret != 0)
    return ret;

  // Now put the rest of bigbuf into the sibling node.
  int currKey;
  PageId currPid;
  for (int j = midKeyIndex + 2*sizeof(int) + 2*sizeof(PageId);
           j < PageFile::PAGE_SIZE;
           j += (sizeof(int) + sizeof(PageId)))
  {
    memcpy(&currKey, bigbuf + j, sizeof(int));
    memcpy(&currPid, bigbuf + j + sizeof(int), sizeof(PageId));

    ret = sibling.insert(currKey, currPid);
    if (ret != 0)
    {
      delete [] bigbuf;
      return ret;
    }
  }

  delete [] bigbuf;

  return 0;
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{
  int i;
  for (i = 0; i < BTNLN_MAX_KEYS; ++i)
    if (searchKey < getKeyAtEid(i))
      break;

  pid = getPidAfterEid(i-1);
  return 0;
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{
  memset(buffer, 0, PageFile::PAGE_SIZE);
  memcpy(buffer, &pid1, sizeof(pid1));
  memcpy(buffer + sizeof(pid1), &key, sizeof(key));
  memcpy(buffer + sizeof(pid1) + sizeof(key), &pid2, sizeof(pid2));
  m_numkeys = 1;

  return 0;
}

void BTNonLeafNode::printBuffer()
{
  printBytes(buffer);
}

int BTNonLeafNode::getKeyAtEid(int eid)
{
  int offset = sizeof(PageId) + eid*(sizeof(int) + sizeof(PageId));
  return ((int *) buffer)[offset/sizeof(int)];
}

PageId BTNonLeafNode::getPidAfterEid(int eid)
{
  int offset = sizeof(PageId) + eid*(sizeof(int) + sizeof(PageId));
  return ((PageId*) buffer)[offset/sizeof(PageId) + 1];
}
/*
int main() {
	BTLeafNode* leaf = new BTLeafNode();

	int numLeaves = leaf->getKeyCount();
	cout << "number of leaves: " << numLeaves << endl;

	RecordId testrid;
	testrid.pid = 100;
	testrid.sid = 200;
	leaf->insert(300,testrid);

	numLeaves = leaf->getKeyCount();
	cout << "number of leaves: " << numLeaves << endl;

	testrid.pid = 300;
	testrid.sid = 400;
	leaf->insert(500,testrid);

	numLeaves = leaf->getKeyCount();
	cout << "number of leaves: " << numLeaves << endl;

	int eid;
	leaf->locate(400, eid);
	cout << "eid: " << eid << endl;

	testrid.pid = 100;
	testrid.sid = 200;
	leaf->insert(100,testrid);

	numLeaves = leaf->getKeyCount();
	cout << "number of leaves: " << numLeaves << endl;

	leaf->locate(50,eid);
	cout << "eid: " << eid << endl;

	testrid.pid = 300;
	testrid.sid = 400;
	leaf->insert(400,testrid);

	numLeaves = leaf->getKeyCount();
	cout << "number of leaves: " << numLeaves << endl;

	leaf->locate(350,eid);
	cout << "eid: "  << eid << endl;

	int key;
	leaf->readEntry(2,key,testrid);
	cout << "key at eid 2: " << key << endl;
	cout << "pageid at eid 2: " << testrid.pid << endl;
	cout << "sid at eid 2: " << testrid.sid << endl;

	PageId nextpg = 512;
	leaf->setNextNodePtr(nextpg);
	PageId respg = leaf->getNextNodePtr();
	cout << "next page ptr: " << respg << endl;

  cout << "----------------------------------------" <<
          "----------------------------------------" << endl;
  cout << "Non Leaf Node Testing" << endl;
  cout << "----------------------------------------" <<
          "----------------------------------------" << endl;

  BTNonLeafNode * nl = new BTNonLeafNode();

  PageId p1 = 1;
  int k1 = 10;
  int k2 = k1+7;

  RC ret;

  cout << "******* Test BTNLN Insert *******" << endl;

  ret = nl->initializeRoot(p1, k1, p1);
  if (ret == 0)
    cout << "Initialize node to " << k1 << endl;
  else
    cout << "Couldn't initialize node." << endl;

  for (int i = k2; i < k2+BTNLN_MAX_KEYS-1-1; ++i)
  {
    ret = nl->insert(i, ++p1);
    if (ret == 0)
      cout << "Added node #" << i << endl;
    else
      cout << "Couldn't add node #" << i << endl;
  }

  cout << "NL Key Count: " << nl->getKeyCount() << endl;

  int i = (k2 + k1)/2;
  ret = nl->insert(i, ++p1);
  if (ret == 0)
    cout << "Added node #" << i << endl;
  else
    cout << "Couldn't add node #" << i << endl;

  for (int i = 0; i < BTNLN_MAX_KEYS; ++i)
    cout << nl->getKeyAtEid(i) << " ";
  cout << endl;

  cout << "Node full? " << ((nl->insert(400, 400) == RC_NODE_FULL) ? "yes" : "no") << endl;

  cout << "NL Key Count: " << nl->getKeyCount() << endl;

  cout << "******* Test BTNLN Insert and Split *******" << endl;

  BTNonLeafNode * sibling = new BTNonLeafNode();
  int midKey;
  ret = nl->insertAndSplit(14, 20, *sibling, midKey);

  for (int i = 0; i < BTNLN_MAX_KEYS; ++i)
    cout << nl->getKeyAtEid(i) << " ";
  cout << endl;
  for (int i = 0; i < BTNLN_MAX_KEYS; ++i)
    cout << sibling->getKeyAtEid(i) << " ";
  cout << endl;

  delete sibling;

  cout << "******* Test BTLN Insert *******" << endl;

  key = 500;
  do {
  } while (leaf->insert(++key, testrid) != RC_NODE_FULL);

  for (int i = 0; i < BTLN_MAX_KEYS; ++i)
    cout << leaf->getKeyAtEid(i) << " " ;
  cout << endl;

  cout << "******* Test BTLN Insert and Split *******" << endl;

  BTLeafNode * lsib = new BTLeafNode();
  int sibKey;
  ret = leaf->insertAndSplit(450, testrid, *lsib, sibKey);

  for (int i = 0; i < BTLN_MAX_KEYS; ++i)
    cout << leaf->getKeyAtEid(i) << " " ;
  cout << endl;

  for (int i = 0; i < BTLN_MAX_KEYS; ++i)
    cout << lsib->getKeyAtEid(i) << " " ;
  cout << endl;

  delete lsib;
}
*/
